package com.study.sort;

import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static com.study.sort.BubbleSort.exch;

// 快速排序
public class QuickSort
{
    int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 18, 8};

    // // 2023新版数据结构与算法
    @Test
    void sort1()
    {
        quick(arr, 0, arr.length - 1);
    }

    void quick(int[] arr, int left, int right)
    {
        if (left >= right) return;
        int p = partition(arr, left, right);
        quick(arr, left, p - 1);
        quick(arr, p + 1, right);
    }

    private int partition(int[] arr, int left, int right)
    {
        int pv = arr[left];     // 基准点的元素
        int i = left + 1, j = right;
        while (i < j) {
            // j 找比基准点小的元素
            while (i < j && arr[j] >= pv) {
                j--;
            }
            // i 找比基准点大的元素
            while (i < j && arr[i] <= pv) {
                i++;
            }
            if (i < j) {
                // 左侧大的交换到右边，右侧小的交换到左边
                exch(arr, i, j);
            }
        }
        // 基准点从最左侧归位
        exch(arr, left, i);
        return i;
    }

    // // Java基础 入门到起飞 常见算法
    @Test
    void sort()
    {
        quickSortRecursion(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private void quickSortRecursion(int[] arr, int start, int end)
    {
        int left = start;
        int right = end;

        // 不能写成 ==
        if (left >= right) return;

        // 基准点
        int baseNumber = arr[start];
        while (left < right) {
            // right 找比基准点小的元素
            while (left < right && arr[right] >= baseNumber) {
                right--;
            }
            // left 找比基准点大的元素
            while (left < right && arr[left] <= baseNumber) {
                left++;
            }
            // 找到后，交换 left 和 right
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        // 基准点元素应存入的索引 left
        int temp = arr[start];
        arr[start] = arr[left];
        arr[left] = temp;

        // 递归基准点两边的区间
        quickSortRecursion(arr, start, left - 1);
        quickSortRecursion(arr, left + 1, end);
    }


    @BeforeEach
    void printArrBefore()
    {
        System.out.println(Arrays.toString(arr));
    }

    @AfterEach
    void printArrAfter()
    {
        System.out.println(Arrays.toString(arr));
    }

    // 递归
    public static void main(String[] args)
    {
        System.out.println(getSum(100));
        System.out.println(getFactorialRecursion(5));
    }

    public static int getFactorialRecursion(int number)
    {
        if (number == 1) return 1;
        return number * getFactorialRecursion(number - 1);
    }

    public static int getSum(int number)
    {
        if (number == 1) return 1;
        return number + getSum(number - 1);
    }
}
